package com.lw.leetcode.sort.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * sort
 * 1090. 受标签影响的最大值
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/29 20:21
 */
public class LargestValsFromLabels {

    public static void main(String[] args) {
        LargestValsFromLabels test = new LargestValsFromLabels();

        // 9
//        int[] values = {5, 4, 3, 2, 1};
//        int[] labels = {1, 1, 2, 2, 3};
//        int num_wanted = 3;
//        int use_limit = 1;

        // 534523
        int[] values = {5963, 15066, 7870, 4883, 18205, 19694, 1938, 2291, 13915, 16317, 12347, 19514, 2766, 13578, 18721, 892, 1683, 12691, 6700, 17793, 19514, 10687, 8106, 11006, 11841, 5992, 602, 7538, 13220, 15178, 14142, 7813, 17632, 16438, 3652, 9630, 19297, 19328, 12118, 18871, 1024, 10888, 2668, 6695, 6990, 8680, 13515, 10150, 6218, 18402};
        int[] labels = {7149, 19554, 17254, 15626, 5710, 9132, 9068, 1432, 14982, 3596, 12403, 1746, 10231, 11836, 449, 15140, 17696, 17094, 795, 4355, 1227, 5973, 18464, 6046, 10232, 5538, 10066, 14692, 18832, 11861, 7265, 13952, 9448, 6164, 14014, 8073, 13446, 18649, 18769, 6285, 13127, 2109, 13319, 10794, 9828, 15545, 12451, 11604, 4072, 9114};
        int num_wanted = 45;
        int use_limit = 1;

        int i = test.largestValsFromLabels(values, labels, num_wanted, use_limit);
        System.out.println(i);
    }

    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        int length = values.length;
        for (int i = 0; i < length; i++) {
            labels[i] |= (values[i] << 16);
        }
        Arrays.sort(labels);
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for (int i = length - 1; i >= 0; i--) {
            int l = labels[i] & 0XFFFF;
            int c = map.getOrDefault(l, 0);
            if (c < useLimit) {
                sum += (labels[i] >> 16);
                count++;
                map.put(l, c + 1);
                if (count == numWanted) {
                    break;
                }
            }
        }
        return sum;
    }

}
